# -*- coding = utf-8 -*-
# @Time : 2021/12/2 16:41
# @Author : chenxingjia
# @File : 多重背包.py


# 转换成0-1背包
def multi_bag_to_01(weights, values, nums, bag_weight):
    new_weights = []
    for i in range(len(weights)):
        for j in range(nums[i]):
            new_weights.append(weights[i])
    l = len(new_weights)
    dp = [0] * (bag_weight+1)
    for j in range(l):
        for i in range(bag_weight, bag_weight-new_weights[j], -1):
                    dp[i] = max(dp[i], dp[i-new_weights[j]]+values[j])
    return dp[-1]
